#!/usr/bin/env python3


def __max_sub_array(a, l, r):
    if l >= r-1:
        return (l, r, a[l])
    m = (l+r)//2
    pl1, pl2, vl = __max_sub_array(a, l, m)
    pr1, pr2, vr = __max_sub_array(a, m, r)
    sum1, max1 = a[m-1], a[m-1]
    i = m - 2
    p1 = m - 1
    while i >= l:
        sum1 += a[i]
        if sum1 > max1:
            max1 = sum1
            p1 = i
        i -= 1
    
    sum2, max2 = a[m], a[m]
    p2 = m
    i = m+1
    while i < r:
        sum2 += a[i]
        if sum2 > max2:
            max2 = sum2
            p2 = i
        i += 1
    p2 += 1
    max = max1 + max2

    if vl > max:
        max = vl
        p1, p2 = pl1, pl2
    elif vr > max:
        max = vr
        p1, p2 = pr1, pr2
    return (p1, p2, max)

def max_sub_array1(a):
    return __max_sub_array(a, 0, len(a))

def max_sub_array2(a):
    sum = 0
    max = a[0]
    p1, p2 = 0, 0
    for i in range(len(a)):
        if sum < 0:
            sum = a[i]
            p1 = i
        else:
            sum += a[i]
        if max < sum:
            max = sum
            p2 = i
    if p1 > p2:
        p1 = p2
    return p1, p2+1, max

if __name__ == "__main__":
    #a = [10, -1, 7, -3]
    #a = [1, -2, 3, 2, -2, 5, -1]
    a = [-1, -2, -3, -2, -2, -5, -8]
    p1, p2, sub_a = max_sub_array1(a)
    print('origion a[%d,%d]:%s'% (0, len(a), a))
    print('sub_a[%d,%d], max is %s' % (p1, p2, sub_a))
    p1, p2, sub_a = max_sub_array2(a)
    print('sub_a[%d,%d], max is %s' % (p1, p2, sub_a))
    #raw_input("Press any key:")